package learn.java;
public class FastSort
    {
        public int getMiddle(List<Integer> list, int low,int high)
        {
            int tmp=list.get(low);
            while(low<high)
            {
                while(low<high&&list.get(high)>tmp)
                {
                    high--;
                }
               list.change(list.get(high),low);
                while(low<high&&list.get(low)<tmp)
                {
                    low++;
                }
                list.change(list.get(low),high);
            }
            list.change(tmp,low);
            return low;
        }
        public void Sort(List<Integer> list, int low, int high)
        {
            if(low<high)
            {
                int middle=getMiddle(list,low,high);
                Sort(list,low,middle-1);
                Sort(list,middle+1,high);
            }
            else return;
        }
        public static void main(String [] args)
        {
            Integer [] list={34,78,23,1,4,89,30};
            List<Integer> demoList=new List<Integer>();
            demoList.initialItems(list);
            System.out.println("the list before sorting:");
            for(int i=0;i<demoList.size();i++)
           {
               System.out.println(demoList.get(i));
            }
            FastSort fs=new FastSort();
            fs.Sort(demoList,0,demoList.size()-1);
            System.out.println("the list after fast sorting:");
            for(int i=0;i<demoList.size();i++)
            {
                System.out.println(demoList.get(i));
            }
        }

    }
